package com.wwz.leetcode;

import com.wwz.common.ListNode;
import org.junit.Test;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
 * 内存消耗：39.3 MB, 在所有 Java 提交中击败了91.18%的用户
 * 哈哈哈 一遍通过 我太强了
 */
public class LeetCode19 {


    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode tail = head;
        int size = 1;
        while (tail.next != null) {
            tail = tail.next;
            size++;
        }

        // index 表示需要移动的次数
        int index = size - n;
        ListNode find = head;
        ListNode pre = head;
        // 如果是头节点被移除 特殊处理
        if (index == 0) {
            return head.next;
        }

        for (int i = 0; i < index; i++) {
            find = find.next;
            // 少移动一次就是前一个了
            if (i != 0) {
                pre = pre.next;
            }
        }
        pre.next = find.next;

        return head;
    }

    @Test
    public void test() {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        System.out.println(removeNthFromEnd(head, 2));
    }

}
